/**
 * @file     intersect.ts
 * @brief    [350. 两个数组的交集 II](https://leetcode.cn/problems/intersection-of-two-arrays-ii/description/)
 * @author   Zhu
 * @date     2023-02-14 00:19
 */

/**
 * 哈希查找
 */
function intersect(nums1: number[], nums2: number[]): number[] {
    function getDict(nums: number[]) {
        const dict = {};
        for (const num of nums) {
            dict[num] = (dict[num] ?? 0) + 1;
        }
        return dict;
    }

    // make sure nums1 is shorter than nums2
    if (nums1.length > nums2.length) {
        let temp = nums1;
        nums1 = nums2;
        nums2 = temp;
    }

    // use the shorter one to make a dictionary
    const dict = getDict(nums1);

    const result: number[] = [];
    // look up in the longer one
    for (const num of nums2) {
        if (!dict[num]) continue;
        result.push(num);
        dict[num]--;
    }

    return result;
}

/**
 * 排序 + 双指针
 */
function intersect(nums1: number[], nums2: number[]): number[] {
    // sort
    const ascend = (a: number, b: number) => a - b;
    nums1.sort(ascend);
    nums2.sort(ascend);

    let i = 0;
    let j = 0;

    const result: number[] = [];
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            i++;
        } else if (nums1[i] > nums2[j]) {
            j++;
        } else {
            result.push(nums1[i]);
            i++;
            j++;
        }
    }

    return result;
}
